package com.yehui.algorithm.sword;

/**
 * 给定一颗二叉搜索树，请找出其中的第k小的结点
 * Created by XuChunH on 2016/9/18.
 */
public class KthNodeBSearchTree {

    int index;

    public TreeNode solution(TreeNode pRoot, int k) {
        if (pRoot == null || k < 1) {
            return null;
        }
        index = 0;
        return find(pRoot, k);
    }

    private TreeNode find(TreeNode root, int k) {
        if (root != null) {
            TreeNode node = find(root.left, k);
            if (node != null) {
                return node;
            }
            index++;
            if (index == k) {
                return root;
            }
            node = find(root.right, k);
            if (node != null) {
                return node;
            }
        }
        return null;
    }

}
